using System;

namespace Test.ConsoleProgram.Algorithm.Solution
{
    [TestDescription("算法: 0142. 环形链表 II")]
    public class No0142_DetectCycle : AbsBaseTestItem
    {
        /*
        给定一个链表，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。

        为了表示给定链表中的环，我们使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。 如果 pos 是 -1，则在该链表中没有环。

        说明：不允许修改给定的链表。

        进阶：
            你是否可以不用额外空间解决此题？
        */

        public class ListNode
        {
            public int val;
            public ListNode next;
            public ListNode(int x)
            {
                val = x;
                next = null;
            }
        }

        public override void OnTest()
        {
            Func<ListNode, ListNode, bool> equalsMethod = (n1, n2) =>
            {
                if (n1 == null && n2 == null) return true;
                return n1.val == n2.val && n1.GetHashCode() == n2.GetHashCode();
            };

            // 示例 1:
            ListNode node = new ListNode(3)
            {
                next = new ListNode(2)
                {
                    next = new ListNode(0)
                    {
                        next = new ListNode(-4),
                    },
                },
            };
            node.next.next.next.next = node.next;
            Assert.TestExe(DetectCycle, node, equalsMethod, node.next);

            // 示例 2:
            node = new ListNode(1)
            {
                next = new ListNode(2),
            };
            node.next.next = node;
            Assert.TestExe(DetectCycle, node, equalsMethod, node);

            // 示例 3:
            node = new ListNode(1);
            Assert.TestExe(DetectCycle, node, equalsMethod, (ListNode)null);
        }

        public ListNode DetectCycle(ListNode head)
        {
            if (head == null)
            {
                return null;
            }
            ListNode slow = head, fast = head;
            while (fast != null)
            {
                slow = slow.next;
                if (fast.next != null)
                {
                    fast = fast.next.next;
                }
                else
                {
                    return null;
                }
                if (fast == slow)
                {
                    ListNode ptr = head;
                    while (ptr != slow)
                    {
                        ptr = ptr.next;
                        slow = slow.next;
                    }
                    return ptr;
                }
            }
            return null;
        }
    }
}
